#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2021/12/27 14:25
# @Software: PyCharm
# @File    : l76_edit_distance.py


class Solution:
    def __init__(self):
        """
        """
        pass

    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        len1, len2 = len(word1), len(word2)
        if len1 == 0 or len2 == 0:
            return max(len1, len2)
        dp = [[0 for i in range(len1 + 1)] for j in range(len2 + 1)]
        for i in range(0, len1 + 1):
            dp[0][i] = i
        for i in range(0, len2 + 1):
            dp[i][0] = i
        for i in range(1, len2 + 1):
            for j in range(1, len1 + 1):
                w2, w1 = word2[i - 1], word1[j - 1]
                step = 0 if w1 == w2 else 1
                dp[i][j] = min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + step, dp[i - 1][j] + 1)
        print(dp)
        return dp[-1][-1]


if __name__ == '__main__':
    s = Solution()
    w1, w2 = "pneumonoultramicroscopicsilicovolcanoconiosis", "ultramicroscopically"
    # w1, w2 = 'sea', 'eat'
    # w1, w2 = "horse", "ros"
    # w1, w2 = 'a', 'b'
    res = s.minDistance(w1, w2)
    print(res)
